Oracle Machine
   HOME

TheInfoList



OR:

In complexity theory and
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, an oracle machine is an
abstract machine An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pr ...
used to study
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
s. It can be visualized as a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
with a
black box In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any
complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...
. Even
undecidable problem In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
s, such as the
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
, can be used.


Oracles

An oracle machine can be conceived as a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
or a
function problem In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...
. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "
black box In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
" that is able to produce a solution for any instance of a given computational problem: * A decision problem is represented as a set ''A'' of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise. * A function problem is represented by a function ''f'' from natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input ''x'' for ''f''. The solution is the value ''f''(''x''). An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if the problem is a decision problem for a set ''A'' of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of ''A''.


Definitions

There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from van Melkebeek (2000:43). An oracle machine, like a Turing machine, includes: * a work tape: a sequence of cells without beginning or end, each of which may contain a B (for blank) or a symbol from the tape alphabet; * a read/write head, which rests on a single cell of the work tape and can read the data there, write new data, and increment or decrement its position along the tape; * a control mechanism, which can be in one of a finite number of states, and which will perform different actions (reading data, writing data, moving the control mechanism, and changing states) depending on the current state and the data being read. In addition to these components, an oracle machine also includes: * an oracle tape, which is a semi-infinite tape separate from the work tape. The alphabet for the oracle tape may be different from the alphabet for the work tape. * an oracle head which, like the read/write head, can move left or right along the oracle tape reading and writing symbols; * two special states: the ASK state and the RESPONSE state. From time to time, the oracle machine may enter the ASK state. When this happens, the following actions are performed in a single computational step: * the contents of the oracle tape are viewed as an instance of the oracle's computational problem; * the oracle is consulted, and the contents of the oracle tape are replaced with the solution to that instance of the problem; * the oracle head is moved to the first square on the oracle tape; * the state of the oracle machine is changed to RESPONSE. The effect of changing to the ASK state is thus to receive, in a single step, a solution to the problem instance that is written on the oracle tape.


Alternative definitions

There are many alternative definitions to the one presented above. Many of these are specialized for the case where the oracle solves a decision problem. In this case: * Some definitions, instead of writing the answer to the oracle tape, have two special states YES and NO in addition to the ASK state. When the oracle is consulted, the next state is chosen to be YES if the contents of the oracle tape are in the oracle set, and chosen to the NO if the contents are not in the oracle set (Adachi 1990:111). * Some definitions eschew the separate oracle tape. When the oracle state is entered, a tape symbol is specified. The oracle is queried with the number of times that this tape symbol appears on the work tape. If that number is in the oracle set, the next state is the YES state; if it is not, the next state is the NO state (Rogers 1967:129). * Another alternative definition makes the oracle tape read-only, and eliminates the ASK and RESPONSE states entirely. Before the machine is started, the
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
of the oracle set is written on the oracle tape using symbols 0 and 1. The machine is then able to query the oracle by scanning to the correct square on the oracle tape and reading the value located there (Soare 1987:47, Rogers 1967:130). These definitions are equivalent from the point of view of Turing computability: a function is oracle-computable from a given oracle under all of these definitions if it is oracle-computable under any of them. The definitions are not equivalent, however, from the point of view of computational complexity. A definition such as the one by van Melkebeek, using an oracle tape which may have its own alphabet, is required in general.


Complexity classes of oracle machines

The
complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...
of
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
s solvable by an algorithm in class A with an oracle for a language L is called AL. For example, PSAT is the class of problems solvable in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by a deterministic Turing machine with an oracle for the
Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
. The notation AB can be extended to a set of languages B (or a complexity class B), by using the following definition: :A^B = \bigcup_ A^L When a language L is
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
for some class B, then AL=AB provided that machines in A can execute reductions used in the completeness definition of class B. In particular, since SAT is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
with respect to polynomial time reductions, PSAT=PNP. However, if A =
DLOGTIME In computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It must be defined on a random-access Turing machine, since ...
, then ASAT may not equal ANP. (Note that the definition of A^B given above is not completely standard. In some contexts, such as the proof of the
time Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to ...
and
space hierarchy theorem In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For exampl ...
s, it is more useful to assume that the abstract machine defining class A only has access to a single oracle for one language. In this context, A^B is not defined if the complexity class B does not have any complete problems with respect to the reductions available to A.) It is understood that NP ⊆ PNP, but the question of whether NPNP, PNP, NP, and P are equal remains tentative at best. It is believed they are different, and this leads to the definition of the
polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. T ...
. Oracle machines are useful for investigating the relationship between complexity classes P and NP, by considering the relationship between PA and NPA for an oracle A. In particular, it has been shown there exist languages A and B such that PA=NPA and PB≠NPB (Baker, Gill, and Solovay 1975). The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because a proof technique that ''relativizes'' (i.e., unaffected by the addition of an oracle) will not answer the P = NP question. Most proof techniques relativize. One may consider the case where an oracle is chosen randomly from among all possible oracles (an infinite set). It has been shown in this case, that with probability 1, PA≠NPA (Bennett and Gill 1981). When a question is true for almost all oracles, it is said to be true ''for a random oracle''. This choice of terminology is justified by the fact that random oracles support a statement with probability 0 or 1 only. (This follows from
Kolmogorov's zero–one law In probability theory, Kolmogorov's zero–one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, namely a ''tail event of independent σ-algebras'', will either almost surely happen or almost sure ...
.) This is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines; for example, IPA≠PSPACEA for a random oracle A but IP =
PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
(Chang et al., 1994).


Oracles and halting problems

A machine with an oracle for the
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
can determine whether particular Turing machines will halt on particular inputs, but it cannot determine, in general, whether machines equivalent to itself will halt. This creates a hierarchy of machines, each with a more powerful halting oracle and an even harder halting problem. This hierarchy of machines can be used to define the ''
arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
'' (Börger 1989).


Applications to cryptography

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, oracles are used to make arguments for the security of cryptographic protocols where a
hash function A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
is used. A security reduction for the protocol is given in the case where, instead of a hash function, a random oracle answers each query randomly but consistently; the oracle is assumed to be available to all parties including the attacker, as the hash function is. Such a proof shows that unless the attacker solves the hard problem at the heart of the security reduction, they must make use of some interesting property of the hash function to break the protocol; they cannot treat the hash function as a black box (i.e., as a random oracle).


See also

*
Black box group In computational group theory, a black box group (black-box group) is a group ''G'' whose elements are encoded by bit strings of length ''N'', and group operations are performed by an oracle (the "black box"). These operations include: • taki ...
*
Turing reduction In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
*
Interactive proof system In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...
*
Matroid oracle In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or ...


References

* Akeo Adachi, ''Foundations of computation theory'', Ohmsha, 1990. * T. P. Baker, J. Gill, R. Solovay. ''Relativizations of the P =? NP Question''.
SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ...
, 4(4): 431-442 (1975) * C. H. Bennett, J. Gill. ''Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1''. SIAM Journal on Computing, 10(1): 96-113 (1981) * Egon Börger. "Computability, Complexity, Logic". North-Holland, 1989. * Richard Chang, Benny Chor, Oded Goldreich,
Juris Hartmanis Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which establis ...
, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. ''Journal of Computer and System Sciences'', volume 49, issue 1, pp. 24–39. August 1994. . http://citeseer.ist.psu.edu/282397.html * Martin Davis, editor: ''The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions'', Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Gödel, Church, Rosser, Kleene, and Post. *
Christos Papadimitriou Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...
. ''Computational Complexity''. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339–343. *
Hartley Rogers, Jr. Hartley Rogers Jr. (July 6, 1926 – July 17, 2015) was a mathematician who worked in computability theory, and was a professor in the Mathematics Department of the Massachusetts Institute of Technology. Biography Born in 1926 in Buffalo, New York ...
, ''Theory of Recursive Functions and Effective Computability'', McGraw-Hill, 1967. *
Michael Sipser Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massa ...
. ''Introduction to the Theory of Computation''. PWS Publishing, 1997. {{isbn, 0-534-94728-X. Section 9.2: Relativization, pp. 318–321. * Robert I. Soare, ''Recursively Enumerable Sets and Degrees'', Perspectives in Mathematical Logic, Springer, 1987. *
Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
, ''Systems of logic based on ordinals'', Proc. London math. soc., 45, 1939 * Dieter van Melkebeek, ''Randomness and Completeness in Computational Complexity'', Lecture Notes in Computer Science 1950, Springer, 2000. Computability theory Turing machine *